<!DOCTYPE html>
<html lang=en>
<head>
    <!-- so meta -->
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="HandheldFriendly" content="True">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=5" />
    <meta name="description" content="今天看到一个题，二叉树求最大路径和，leecode上还是hard模式，觉得这个题还是很有代表性。 复习下，看看怎么解。因为涉及到二叉树，一般都可分解为子问题去递归处理。 递归框架： 123456789&#96;&#96;&#96;c++void traverse(Node *node) &amp;#123;&#x2F;&#x2F;前序	traverse(node-&gt;left);&#x2F;&#x2F; 中序	traverse(node-&gt;right);&#x2F;&#x2F;">
<meta property="og:type" content="article">
<meta property="og:title" content="二叉树的最大路径和">
<meta property="og:url" content="https://jickyi521.github.io/max-path-sum-of-tree-node/index.html">
<meta property="og:site_name" content="羊锅村钱师傅的小册子">
<meta property="og:description" content="今天看到一个题，二叉树求最大路径和，leecode上还是hard模式，觉得这个题还是很有代表性。 复习下，看看怎么解。因为涉及到二叉树，一般都可分解为子问题去递归处理。 递归框架： 123456789&#96;&#96;&#96;c++void traverse(Node *node) &amp;#123;&#x2F;&#x2F;前序	traverse(node-&gt;left);&#x2F;&#x2F; 中序	traverse(node-&gt;right);&#x2F;&#x2F;">
<meta property="og:locale" content="en_US">
<meta property="article:published_time" content="2023-08-24T08:40:11.000Z">
<meta property="article:modified_time" content="2023-08-24T08:40:11.000Z">
<meta property="article:author" content="Qian Yi">
<meta property="article:tag" content="算法">
<meta name="twitter:card" content="summary">
    
    
      
        
          <link rel="shortcut icon" href="/images/favicon.ico">
        
      
      
        
          <link rel="icon" type="image/png" href="/images/favicon-192x192.png" sizes="192x192">
        
      
      
        
          <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png">
        
      
    
    <!-- title -->
    <title>二叉树的最大路径和</title>
    <!-- async scripts -->
    <!-- Google Analytics -->


    <!-- Umami Analytics -->


    <!-- styles -->
    
<link rel="stylesheet" href="/css/style.css">

    <!-- persian styles -->
    
    <!-- rss -->
    
    
	<!-- mathjax -->
	
<meta name="generator" content="Hexo 6.3.0"></head>

<body class="max-width mx-auto px3 ltr">
    
      <div id="header-post">
  <a id="menu-icon" href="#" aria-label="Menu"><i class="fa-solid fa-bars fa-lg"></i></a>
  <a id="menu-icon-tablet" href="#" aria-label="Menu"><i class="fa-solid fa-bars fa-lg"></i></a>
  <a id="top-icon-tablet" href="#" aria-label="Top" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');" style="display:none;"><i class="fa-solid fa-chevron-up fa-lg"></i></a>
  <span id="menu">
    <span id="nav">
      <ul>
        <!--
       --><li><a href="/">首页</a></li><!--
     --><!--
       --><li><a href="/about/">关于</a></li><!--
     --><!--
       --><li><a href="/archives/">归档</a></li><!--
     --><!--
       --><li><a href="/search/">搜索</a></li><!--
     -->
      </ul>
    </span>
    <br/>
    <span id="actions">
      <ul>
        
        <li><a class="icon" aria-label="Previous post" href="/the-first-teacher-visited-home/"><i class="fa-solid fa-chevron-left" aria-hidden="true" onmouseover="$('#i-prev').toggle();" onmouseout="$('#i-prev').toggle();"></i></a></li>
        
        
        <li><a class="icon" aria-label="Next post" href="/ding-tou-when-market-down/"><i class="fa-solid fa-chevron-right" aria-hidden="true" onmouseover="$('#i-next').toggle();" onmouseout="$('#i-next').toggle();"></i></a></li>
        
        <li><a class="icon" aria-label="Back to top" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fa-solid fa-chevron-up" aria-hidden="true" onmouseover="$('#i-top').toggle();" onmouseout="$('#i-top').toggle();"></i></a></li>
        <li><a class="icon" aria-label="Share post" href="#"><i class="fa-solid fa-share-alt" aria-hidden="true" onmouseover="$('#i-share').toggle();" onmouseout="$('#i-share').toggle();" onclick="$('#share').toggle();return false;"></i></a></li>
      </ul>
      <span id="i-prev" class="info" style="display:none;">Previous post</span>
      <span id="i-next" class="info" style="display:none;">Next post</span>
      <span id="i-top" class="info" style="display:none;">Back to top</span>
      <span id="i-share" class="info" style="display:none;">Share post</span>
    </span>
    <br/>
    <div id="share" style="display: none">
      <ul>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.facebook.com/sharer.php?u=https://jickyi521.github.io/max-path-sum-of-tree-node/"><i class="fab fa-facebook " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://twitter.com/share?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&text=二叉树的最大路径和"><i class="fab fa-twitter " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.linkedin.com/shareArticle?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&title=二叉树的最大路径和"><i class="fab fa-linkedin " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://pinterest.com/pin/create/bookmarklet/?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&is_video=false&description=二叉树的最大路径和"><i class="fab fa-pinterest " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="mailto:?subject=二叉树的最大路径和&body=Check out this article: https://jickyi521.github.io/max-path-sum-of-tree-node/"><i class="fa-solid fa-envelope " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://getpocket.com/save?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&title=二叉树的最大路径和"><i class="fab fa-get-pocket " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://reddit.com/submit?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&title=二叉树的最大路径和"><i class="fab fa-reddit " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.stumbleupon.com/submit?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&title=二叉树的最大路径和"><i class="fab fa-stumbleupon " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://digg.com/submit?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&title=二叉树的最大路径和"><i class="fab fa-digg " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.tumblr.com/share/link?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&name=二叉树的最大路径和&description="><i class="fab fa-tumblr " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://news.ycombinator.com/submitlink?u=https://jickyi521.github.io/max-path-sum-of-tree-node/&t=二叉树的最大路径和"><i class="fab fa-hacker-news " aria-hidden="true"></i></a></li>
</ul>

    </div>
    
    
  </span>
</div>

    
    <div class="content index py4 ">
        
        <article class="post h-entry" itemscope itemtype="http://schema.org/BlogPosting">
  <header>
    
    <h1 class="posttitle p-name" itemprop="name headline">
        二叉树的最大路径和
    </h1>



    <div class="meta">
      <span class="author p-author h-card" itemprop="author" itemscope itemtype="http://schema.org/Person">
        <span class="p-name" itemprop="name">Qian Yi</span>
      </span>
      
    <div class="postdate">
      
        <time datetime="2023-08-24T08:40:11.000Z" class="dt-published" itemprop="datePublished">2023-08-24</time>
        
      
    </div>


      
    <div class="article-category">
        <i class="fa-solid fa-archive"></i>
        <a class="category-link" href="/categories/%E6%8A%80%E6%9C%AF/">技术</a>
    </div>


      
    <div class="article-tag">
        <i class="fa-solid fa-tag"></i>
        <a class="p-category" href="/tags/%E7%AE%97%E6%B3%95/" rel="tag">算法</a>
    </div>


    </div>
  </header>
  

  <div class="content e-content" itemprop="articleBody">
    <p>今天看到一个题，<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/binary-tree-maximum-path-sum/solutions/">二叉树求最大路径和</a>，leecode上还是hard模式，觉得这个题还是很有代表性。</p>
<p>复习下，看看怎么解。因为涉及到二叉树，一般都可分解为子问题去递归处理。</p>
<p><code>递归框架</code>：</p>
<figure class="highlight markdown"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="code">```c++</span></span><br><span class="line"><span class="code">void traverse(Node *node) &#123;</span></span><br><span class="line"><span class="code">//前序</span></span><br><span class="line"><span class="code">	traverse(node-&gt;left);</span></span><br><span class="line"><span class="code">// 中序</span></span><br><span class="line"><span class="code">	traverse(node-&gt;right);</span></span><br><span class="line"><span class="code">// 后序</span></span><br><span class="line"><span class="code">&#125;  </span></span><br><span class="line"><span class="code">```</span></span><br></pre></td></tr></table></figure>

<p>最重要的还是要理解这个<code>子问题</code>，怎么定义。</p>
<p>想象下自己在这颗二叉树进行遍历，先进入root节点， 接下来有很多选择，要选最大的子树边距去走。</p>
<p>子树有自己的左子树和右子树。这颗子树对于父亲节点而言，需要交付给父亲节点是：</p>
<p>包含自己(subNode-&gt;val)的最大边距是多少？</p>
<blockquote>
<p>子问题：subMaxPath &#x3D; subNode-&gt;val+max(subNode-&gt;left, subNode-&gt;right)</p>
</blockquote>
<p>整体的结构：</p>
<figure class="highlight markdown"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="code">```c++</span></span><br><span class="line"><span class="code">		int res = INT_MIN;</span></span><br><span class="line"><span class="code">		</span></span><br><span class="line"><span class="code">    //后序遍历可以先知道左节点和右节点</span></span><br><span class="line"><span class="code">    //这个递归函数返回的是当前这个节点最大的路径和</span></span><br><span class="line"><span class="code">    int def(TreeNode* root) &#123;</span></span><br><span class="line"><span class="code"></span></span><br><span class="line"><span class="code">        if(root == nullptr) return 0;</span></span><br><span class="line"><span class="code"></span></span><br><span class="line"><span class="code">        //左右两边节点最大值</span></span><br><span class="line"><span class="code">        int left = max(0, def(root-&gt;left));</span></span><br><span class="line"><span class="code">        int right = max(0, def(root-&gt;right));</span></span><br><span class="line"><span class="code"></span></span><br><span class="line"><span class="code">        //节点的最大路径取决于该节点的值，左右节点的最大路径</span></span><br><span class="line"><span class="code">        res = max(res, left+right+root-&gt;val);</span></span><br><span class="line"><span class="code"></span></span><br><span class="line"><span class="code">        //因为总要选一边所以是max，左右子树，选最大的那颗树</span></span><br><span class="line"><span class="code">        //想象下自己在游走这颗二叉树</span></span><br><span class="line"><span class="code">        return max(left, right)+root-&gt;val;</span></span><br><span class="line"><span class="code">    &#125;</span></span><br><span class="line"><span class="code">    </span></span><br><span class="line"><span class="code">    int maxPathSum(TreeNode* root) &#123;</span></span><br><span class="line"><span class="code">        def(root);</span></span><br><span class="line"><span class="code">        return res;</span></span><br><span class="line"><span class="code">    &#125;  </span></span><br><span class="line"><span class="code">```</span></span><br></pre></td></tr></table></figure>

<p>递归里面，需要想清楚子问题的定义，和return出口的定义。</p>
<p>整个框架结构就清晰了。</p>
<p>算法是软肋，之前面试，有好几个不错的机会，在算法这一轮挂了。<br>尤其是那些从硅谷回来的CTO，喜欢跟你聊算法，测验你的最基础的技术功底如何。<br>也是万万没想到，最后一轮还要搞算法，当时汗都快下来了。<br>有时间应该多补补这块，算是给脑子健健脑。</p>
<p>即使不干技术这行了，也是有意义的。</p>

  </div>
</article>

    <div class="blog-post-comments">
        <div id="disqus_thread">
            <noscript>Please enable JavaScript to view the comments.</noscript>
        </div>
    </div>



        
          <div id="footer-post-container">
  <div id="footer-post">

    <div id="nav-footer" style="display: none">
      <ul>
        
          <li><a href="/">首页</a></li>
        
          <li><a href="/about/">关于</a></li>
        
          <li><a href="/archives/">归档</a></li>
        
          <li><a href="/search/">搜索</a></li>
        
      </ul>
    </div>

    
    

    <div id="share-footer" style="display: none">
      <ul>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.facebook.com/sharer.php?u=https://jickyi521.github.io/max-path-sum-of-tree-node/"><i class="fab fa-facebook fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://twitter.com/share?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&text=二叉树的最大路径和"><i class="fab fa-twitter fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.linkedin.com/shareArticle?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&title=二叉树的最大路径和"><i class="fab fa-linkedin fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://pinterest.com/pin/create/bookmarklet/?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&is_video=false&description=二叉树的最大路径和"><i class="fab fa-pinterest fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="mailto:?subject=二叉树的最大路径和&body=Check out this article: https://jickyi521.github.io/max-path-sum-of-tree-node/"><i class="fa-solid fa-envelope fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://getpocket.com/save?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&title=二叉树的最大路径和"><i class="fab fa-get-pocket fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://reddit.com/submit?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&title=二叉树的最大路径和"><i class="fab fa-reddit fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.stumbleupon.com/submit?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&title=二叉树的最大路径和"><i class="fab fa-stumbleupon fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://digg.com/submit?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&title=二叉树的最大路径和"><i class="fab fa-digg fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.tumblr.com/share/link?url=https://jickyi521.github.io/max-path-sum-of-tree-node/&name=二叉树的最大路径和&description="><i class="fab fa-tumblr fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://news.ycombinator.com/submitlink?u=https://jickyi521.github.io/max-path-sum-of-tree-node/&t=二叉树的最大路径和"><i class="fab fa-hacker-news fa-lg" aria-hidden="true"></i></a></li>
</ul>

    </div>

    <div id="actions-footer">
        <a id="menu" class="icon" href="#" onclick="$('#nav-footer').toggle();return false;"><i class="fa-solid fa-bars fa-lg" aria-hidden="true"></i> Menu</a>
        
        <a id="share" class="icon" href="#" onclick="$('#share-footer').toggle();return false;"><i class="fa-solid fa-share-alt fa-lg" aria-hidden="true"></i> Share</a>
        <a id="top" style="display:none" class="icon" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fa-solid fa-chevron-up fa-lg" aria-hidden="true"></i> Top</a>
    </div>

  </div>
</div>

        
        <footer id="footer">
  <div class="footer-left">
    Copyright &copy;
    
    
    2023-2024
    Qian Yi
  </div>
  <div class="footer-right">
    <nav>
      <ul>
        <!--
       --><li><a href="/">首页</a></li><!--
     --><!--
       --><li><a href="/about/">关于</a></li><!--
     --><!--
       --><li><a href="/archives/">归档</a></li><!--
     --><!--
       --><li><a href="/search/">搜索</a></li><!--
     -->
      </ul>
    </nav>
  </div>
</footer>

    </div>
    <!-- styles -->



  <link rel="preload" as="style" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.4.0/css/all.min.css" crossorigin="anonymous" onload="this.onload=null;this.rel='stylesheet'"/>


    <!-- jquery -->

  <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.6.0/jquery.min.js" crossorigin="anonymous"></script>




<!-- clipboard -->

  
    <script src="https://cdnjs.cloudflare.com/ajax/libs/clipboard.js/2.0.7/clipboard.min.js" crossorigin="anonymous"></script>
  
  <script type="text/javascript">
  $(function() {
    // copy-btn HTML
    var btn = "<span class=\"btn-copy tooltipped tooltipped-sw\" aria-label=\"Copy to clipboard!\">";
    btn += '<i class="fa-regular fa-clone"></i>';
    btn += '</span>';
    // mount it!
    $(".highlight table").before(btn);
    var clip = new ClipboardJS('.btn-copy', {
      text: function(trigger) {
        return Array.from(trigger.nextElementSibling.querySelectorAll('.code')).reduce((str,it)=>str+it.innerText+'\n','')
      }
    });
    clip.on('success', function(e) {
      e.trigger.setAttribute('aria-label', "Copied!");
      e.clearSelection();
    })
  })
  </script>


<script src="/js/main.js"></script>

<!-- search -->

<!-- Baidu Analytics -->

  <script type="text/javascript">
        var _hmt = _hmt || [];
        (function() {
          var hm = document.createElement("script");
          hm.src = "https://hm.baidu.com/hm.js?1919745cc8ad33b42ca74c37deaafb5b";
          var s = document.getElementsByTagName("script")[0];
          s.parentNode.insertBefore(hm, s);
        })();
        </script>

<!-- Cloudflare Analytics -->

<!-- Disqus Comments -->

    <script type="text/javascript">
        var disqus_shortname = 'jickyi521';

        (function(){
            var dsq = document.createElement('script');
            dsq.type = 'text/javascript';
            dsq.async = true;
            dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
            (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
        }());
    </script>

<!-- utterances Comments -->

</body>
</html>
